class Solution:
    def findNumberIn2DArray(self, matrix: list, target: int) -> bool:
        # 检查 matrix 不为空
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False

        # 开始搜索
        i, j = len(matrix) - 1, 0
        while i >= 0 and j <= len(matrix[0]) - 1:
            if target < matrix[i][j]:
                i -= 1
            elif target > matrix[i][j]:
                j += 1
            else:
                return True

        return False

    def findNumberIn2DArray2(self, matrix: list, target: int) -> bool:
        def bsearch(arr: list, target: int) -> bool:
            i, j = 0, len(arr) - 1
            while i <= j:
                tmp = (i + j) // 2
                if arr[tmp] < target:
                    i = tmp + 1
                elif arr[tmp] > target:
                    j = tmp - 1
                else:
                    return True
            return False

        for i in range(len(matrix)):
            if bsearch(matrix[i], target):
                return True
        return False


if __name__ == '__main__':
    solution = Solution()

    matrix = [
        [1,   4,  7, 11, 15],
        [2,   5,  8, 12, 19],
        [3,   6,  9, 16, 22],
        [10, 13, 14, 17, 24],
        [18, 21, 23, 26, 30]
    ]

    target = 5
    print(f"target = {target}:", solution.findNumberIn2DArray(matrix, target))

    target = 20
    print(f"target = {target}:", solution.findNumberIn2DArray(matrix, target))
